// @algorithm @lc id=639 lang=cpp 
// @title decode-ways-ii


// @test("*")=9
// @test("1*")=18
// @test("2*")=15
#define mod 1000'000'007
class Solution {
    int64_t d0;
    int64_t d1;
public:
    int count(char cur){
        return '0'==cur ? 0 : ('*'==cur ? 9 : 1);
    }
    int count(char pre, char cur){
        if('*'==pre && '*'==cur)
            return 15; // [11,19] [21,26]
        if('*'==pre)
            return cur <= '6' ? 2 : 1;
        if('*'==cur){
            if('1'==pre) return 9;
            if('2'==pre) return 6;
            return 0;
        }
        return '0'<pre && 10*(pre-'0')+(cur-'0')<=26;
    }
    int numDecodings(string s) {
        d0 = 1, d1 = 1;
        int64_t d2 = 0;
        for(int i=1; i<=s.size(); i++){
            d2 = 0;
            if('0' != s[i-1])
                d2 = (d2 + d1*count(s[i-1])) % mod;
            if(1<i)
                d2 = (d2 + d0*count(s[i-2], s[i-1])) % mod;
            d0 = d1;
            d1 = d2;
        }
        return d2;
    }
};